#include "block_sorting.h"

/* inicializar_vectores:
 * esta funcion incializa:
 * 		vec_punteros: es un vector de punteros a los respectivos nodos
 * de la lista circular que posee el texto a comprimir
 * 		vec_ult_col: es un vector que posee el último caracter de las 
 * rotaciones del bloque de texto a comprimir
*/
void inicializar_vectores(tlista lista, tnodol **vec_punteros, unsigned char *vec_ult_col) {
	tlista_iter iter;
	Crear_Lista_Iter(&lista, &iter);	
	int i = 0;
	while (!Lista_Iter_Final(&iter)) {
		vec_punteros[i] = iter.actual;
	    	vec_ult_col[i] = *(char*)iter.anterior->dato;
		Avanzar_Lista_Iter(&iter);
		i++;
	}
}

void swap_compresion(tnodol **vector_punteros, unsigned char *vec_ult_col, int pos1, int pos2, int *rastro) {
	tnodol *aux1 = vector_punteros[pos1];
	char aux2 = vec_ult_col[pos1];
	vector_punteros[pos1] = vector_punteros[pos2];
	vector_punteros[pos2] = aux1;
	vec_ult_col[pos1] = vec_ult_col[pos2];
	vec_ult_col[pos2] = aux2;
	if (*rastro == pos1)
		*rastro = pos2;
	else if (*rastro == pos2)
		*rastro = pos1;
}

// no se si me conviene hacerlo NO case sensitive
int comparar_caracteres(unsigned char caracter1, unsigned char caracter2) {
	if (caracter1 < caracter2)
		return -1;
	else if (caracter1 > caracter2)
		return 1;
	return 0;
}

void quick_sort_compresion(tnodol **vector_punteros, unsigned char *vec_ult_col, int inicio, int fin, int *rastro) {
	if ((fin - inicio) < 2)
		return;
	int izq = inicio + 1;
	int der = fin - 1;
	int pivote = inicio;
	// Cambia el del medio con el primero.
	// (optimización para vectores ordenados).
	int medio = (izq + der) / 2;
	swap_compresion(vector_punteros, vec_ult_col, pivote, medio, rastro);
	while (izq <= der) {
		tnodol *puntero_pivote = vector_punteros[pivote];
		tnodol *puntero_der = vector_punteros[der];
		tnodol *puntero_izq = vector_punteros[izq];
		int comparacion1 = comparar_caracteres(*(unsigned char*)puntero_der->dato, *(unsigned char*)puntero_pivote->dato);
		int comparacion2 = comparar_caracteres(*(unsigned char*)puntero_izq->dato, *(unsigned char*)puntero_pivote->dato);
		tnodol *puntero_der_aux = puntero_der;
		bool dio_vuelta = false;
		while(comparacion1 == 0){
			puntero_der = puntero_der->siguiente;
			puntero_pivote = puntero_pivote->siguiente;
			if (puntero_der_aux == puntero_der) {
				dio_vuelta = true;
				break;
			}
			comparacion1 = comparar_caracteres(*(unsigned char*)puntero_der->dato, *(unsigned char*)puntero_pivote->dato);
		}
		
		puntero_pivote = vector_punteros[pivote];
		tnodol *puntero_izq_aux = puntero_izq;
		while(comparacion2 == 0){				
			puntero_izq = puntero_izq->siguiente;
			puntero_pivote = puntero_pivote->siguiente;
			if (puntero_izq_aux == puntero_izq) {
				dio_vuelta = true;
				break;
			}
			comparacion2 = comparar_caracteres(*(unsigned char*)puntero_izq->dato, *(unsigned char*)puntero_pivote->dato);
		}
		
		if (!dio_vuelta) 
			while ((izq <= der) && (comparacion1 > 0)){
				der--;
				if (der >= 0)
					comparacion1 = comparar_caracteres(*(unsigned char*)vector_punteros[der]->dato, *(unsigned char*)vector_punteros[pivote]->dato);
			}
		else 
			while ((izq <= der) && (comparacion1 >= 0)){
				der--;
				if (der >= 0)
					comparacion1 = comparar_caracteres(*(unsigned char*)vector_punteros[der]->dato, *(unsigned char*)vector_punteros[pivote]->dato);
			}

		while ((izq <= der) && comparacion2 < 0){
			izq++;
			if (izq < fin)
				comparacion2 = comparar_caracteres(*(unsigned char*)vector_punteros[izq]->dato, *(unsigned char*)vector_punteros[pivote]->dato);
		}
		if (izq < der) {
			swap_compresion(vector_punteros, vec_ult_col, izq, der, rastro);
		}
	}
	// Coloca el pivote al final de los menores y el último
	// menor en el primer lugar.
	swap_compresion(vector_punteros, vec_ult_col, pivote, der, rastro);
	// Ordena cada una de las mitades
	quick_sort_compresion(vector_punteros, vec_ult_col, inicio, der, rastro);
	quick_sort_compresion(vector_punteros, vec_ult_col, der+1, fin, rastro);
}


void compresion_ordenar_lexicograficamente(tnodol **vec_punteros, unsigned char *vec_ult_col, int largo, int *rastro) {
	quick_sort_compresion(vec_punteros, vec_ult_col, 0, largo, rastro);
}

void compresion_block_sorting(tlista lista, unsigned char** L, uint32_t *I) {
	int largo_lista = Largo_Lista(lista);
	tnodol *vec_punteros [largo_lista];
	unsigned char *vec_ult_col = (unsigned char*) malloc (sizeof(char) * largo_lista);
	int rastro = 0;
	inicializar_vectores(lista, vec_punteros, vec_ult_col);
	compresion_ordenar_lexicograficamente(vec_punteros, vec_ult_col, largo_lista, &rastro);
	*L = vec_ult_col;
	*I = rastro;
}

void swap_descompresion(unsigned char *vec_ult_col, int *vec_indices, int pos1, int pos2) {
	char aux1 = vec_ult_col[pos1];
	int aux2 = vec_indices[pos1];
	vec_ult_col[pos1] = vec_ult_col[pos2];
	vec_ult_col[pos2] = aux1;
	vec_indices[pos1] = vec_indices[pos2];
	vec_indices[pos2] = aux2;
}



void merge (unsigned char* vec_ult_col, int *vec_indices, int inicio, int medio, int fin, unsigned char aux[], int aux2[]){
	int pos_1 = inicio;
	int pos_2 = medio;
	int pos_a = inicio;
	// Intercala ordenadamente
	while ( (pos_1 < medio) && (pos_2 < fin) ) {
		if (vec_ult_col[pos_1] <= vec_ult_col[pos_2]) {
			aux[pos_a] = vec_ult_col[pos_1];
			aux2[pos_a] = vec_indices[pos_1];
			pos_a++; pos_1++;
		} 
		else {
			aux[pos_a] = vec_ult_col[pos_2];
			aux2[pos_a] = vec_indices[pos_2];
			pos_a++; pos_2++;
		}
	}
	// Copia lo que haya quedado al final del primer vector
	while (pos_1 < medio) {
		aux[pos_a] = vec_ult_col[pos_1];
		aux2[pos_a] = vec_indices[pos_1];
		pos_a++; pos_1++;
	}
	// Copia lo que haya quedado al final del segundo vector
	while (pos_2 < fin) {
		aux[pos_a] = vec_ult_col[pos_2];
		aux2[pos_a] = vec_indices[pos_2];
		pos_a++; pos_2++;
	}

// Copia los valores del vector auxiliar al original
	int i;
	for (i = inicio; i < fin; i++) {
		vec_ult_col[i] = aux[i];
		vec_indices[i] = aux2[i];
	}
}


void msort(unsigned char* vec_ult_col, int *vec_indices, int inicio, int fin, unsigned char aux[], int aux2[]){
	int largo = fin - inicio;
	if (largo == 1) {
		aux[inicio] = vec_ult_col[inicio];
		aux2[inicio] = vec_indices[inicio];
		return;
	}
	int medio = inicio + (largo / 2);
	msort (vec_ult_col,vec_indices, inicio, medio, aux, aux2);
	msort (vec_ult_col,vec_indices, medio, fin, aux, aux2);
	merge (vec_ult_col,vec_indices, inicio, medio, fin, aux, aux2);
}


void merge_sort_descompresion(unsigned char *vec_ult_col, int *vec_indices, int largo){
	unsigned char aux[largo];
	int aux2[largo];
	msort(vec_ult_col, vec_indices, 0, largo, aux, aux2);
}

void descompresion_ordenar_lexicograficamente(unsigned char *vec_ult_col, int *vec_indices, int largo) {
	merge_sort_descompresion(vec_ult_col, vec_indices, largo);
}

void descompresion_block_sorting(unsigned char* texto, unsigned char *vector_caracteres, int I, int largo) {
	int vec_indices[largo];
	int i;
	for(i = 0; i < largo; i++) {
		vec_indices[i] = i;
	}
	descompresion_ordenar_lexicograficamente(vector_caracteres, vec_indices, largo);
	for(i = 0; i < largo; i++) {
		texto[i] = vector_caracteres[I];
		I = vec_indices[I];
	}
}
